/*
 * @lc app=leetcode.cn id=138 lang=java
 *
 * [138] 随机链表的复制
 */

// @lc code=start
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

import java.util.HashMap;
import java.util.Map;
class Solution {
    public Node copyRandomList(Node head) {
        // if(head == null) {
        //     return null;
        // }

        // // 1. 复制链表---将新结点插入到原结点后面
        // for(Node node = head; node != null; node = node.next.next) {
        //     Node nodeNew = new Node(node.val);
        //     nodeNew.next = node.next;
        //     node.next = nodeNew;
        // }

        // // 2. 复制random指针
        // for(Node node = head; node != null; node = node.next.next) {
        //     Node nodeNew = node.next;
        //     nodeNew.random = (node.random != null) ? node.random.next : null;
        // }

        // // 3. 拆分链表
        // Node headNew = head.next;
        // for(Node node = head; node != null; node = node.next) {
        //     Node nodeNew = node.next;
        //     node.next = node.next.next;
        //     nodeNew.next = (nodeNew.next != null) ? nodeNew.next.next : null;
        // }

        // return headNew;
        
        // 使用hash表实现
        if(head == null) {
            return null;
        }
        Node cur = head;
        Map<Node, Node> map = new HashMap<>();

        while(cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }

        cur = head;
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}
// @lc code=end

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}